#include "avl_tree.h"
#include <stdexcept>

template <class Comparable>
AvlTree<Comparable>::AvlTree(): root(NULL)
{

}

template <class Comparable>
AvlTree<Comparable>::~AvlTree()
{
	makeEmpty();
}

template <class Comparable>
const Comparable & 
AvlTree<Comparable>::findMin() const
{
	if (isEmpty())
		range_error("tree empty");

	return findMin(root)->element;
}

template <class Comparable>
const Comparable & 
AvlTree<Comparable>::findMax() const
{
	if (isEmpty())
		range_error("tree empty");

	return findMax(root)->element;
}

template <class Comparable>
bool AvlTree<Comparable>::contains(const Comparable &x) const
{
	if (isEmpty())
		range_error("tree empty");
	return contains(x, root);
}

template <class Comparable>
bool AvlTree<Comparable>::isEmpty() const
{
	return root == NULL;
}

template <class Comparable>
void AvlTree<Comparable>::printTree() const
{
	if (isEmpty())
		cout << "Empty tree" << endl;
	else 
		printTree(root);
}

template <class Comparable>
void AvlTree<Comparable>::makeEmpty() 
{
	makeEmpty(root);
}

template <class Comparable>
void AvlTree<Comparable>::insert(const Comparable &x) 
{
	insert(x, root);
}

template <class Comparable>
void AvlTree<Comparable>::remove(const Comparable &x)
{
	cout << "Sorry, remove unimplemented;" << x <<
			"still present" << endl;
}

template <class Comparable>
const AvlTree<Comparable> & AvlTree<Comparable>::operator=(const AvlTree &rhs)
{
	if (this != &rhs){
		makeEmpty();	
		root = clone(rhs.root);
	}
	return *this;
	
}

/*
 *Return max value betweee a and b.
 */
template <class Comparable>
int AvlTree<Comparable>::max(int a, int b) const
{
	return a > b ? a : b;
}

/*
 *Return the height of node t, or -1 if NULL.
 */
template <class Comparable>
int AvlTree<Comparable>::height(AvlNode *t) const
{
	return t == NULL ? -1 : t->height;
}

/*
 *Internal method to insert into a subtree.
 *x is the item to insert.
 *t is the node that roots the tree.
 */
template <class Comparable>
void AvlTree<Comparable>::insert(const Comparable &x, 
 								 AvlNode * &t) const
{
	if (t == NULL)
		t = new AvlNode(x, NULL, NULL);
	else if (x < t->element) {
		insert(x, t->left);	
		if (height(t->left) - height(t->right) == 2)
			if (x < t->left->element)
				rotateWithLeftChild(t);
			else
				doubleWithLeftChild(t);
	}
	else if (t->element < x) {
		insert(x, t->right);	
		if (height(t->right) - height(t->left) == 2)
			if (t->right->element < x)
				rotateWithRightChild(t);
			else 
				doubleWithRightChild(t);
	}
	else 
		;
	t->height = max(height(t->left), height(t->right)) + 1;
}

/*
 *Rotate binary tree node with left child.
 *For AVL trees, this is a single rotation for case 1.
 *Update heights, then set new root.
 */
template <class Comparable>
void AvlTree<Comparable>::
rotateWithLeftChild(AvlNode * &k2) const
{
	AvlNode *k1 = k2->left;
	k2->left = k1->right;
	k1->right = k2;
	k2->height = max(height(k2->left), height(k2->right)) + 1;
	k1->height = max(height(k1->left), k2->height) + 1;
	k2 = k1; // set new root
}

/*
 *Rotate binary tree node with right child. 
 *Symmetric with code above.
 * ---------------------------------------add by listar
 */
template <class Comparable>
void AvlTree<Comparable>::
rotateWithRightChild(AvlNode * &k1) const
{
	AvlNode *k2 = k1->right;	
	k1->right = k2->left;
	k2->left = k1;
	k1->height = max(height(k1->right), height(k1->left)) + 1;
	k2->height = max(height(k2->right), k1->height) + 1;
	k1 = k2;
}

/*
 *Double rotate binary tree node: first left child.
 *with its right child; then node k3 with new left child.
 *For AVL trees, this is a double rotation for case 2.
 *Update heights, then set new root.
 */
template <class Comparable>
void AvlTree<Comparable>::
doubleWithLeftChild(AvlNode * &k3) const
{
	rotateWithRightChild(k3->left);
	rotateWithLeftChild(k3);
}

/*
 *Double rotate binary tree node: first right child.
 *Symmtric with code above.
 */
template <class Comparable>
void AvlTree<Comparable>::
doubleWithRightChild(AvlNode * &k3) const
{
	rotateWithLeftChild(k3->right);
	rotateWithRightChild(k3);
}

/*
 *template <class Comparable>
 *AvlTree<Comparable>::AvlNode * AvlTree<Comparable>::findMin(AvlNode *t) const
 *{
 *    if (t == NULL)	
 *        return NULL;
 *    if (t->left == NULL)
 *        return t;
 *    return findMin(t->left);
 *}
 */

/*
 *template <class Comparable>
 *AvlTree<Comparable>::AvlNode * AvlTree<Comparable>::findMax(AvlNode *t) const
 *{
 *    if (t != NULL)
 *        while (t->right != NULL)
 *            t = t->right;
 *    
 *    return t;
 *}
 */

template <class Comparable>
bool AvlTree<Comparable>::contains(const Comparable &x, AvlNode *t) const
{
    /* // reciursive version
	 *if (t == NULL)
	 *    return false;
	 *else if (x < t->element)
	 *    return contains(x, t->left);
	 *else if (x > t->element) 
	 *    return contains(x, t->right);
	 *else 
	 *    return true;
     */

	while (t != NULL)
		if (x < t->element)
			t = t->left;
		else if (x > t->element)
			t = t->right;
		else 
			return true;
	
	return false;
}

template <class Comparable>
void AvlTree<Comparable>::makeEmpty(AvlNode * &t) const
{
	if (t != NULL){
		makeEmpty(t->left);	
		makeEmpty(t->right);
		delete t;
	}

	t = NULL;
}

template <class Comparable>
void AvlTree<Comparable>::printTree(AvlNode *t) const
{
	 if (t != NULL) {
		printTree(t->left); 
		cout << t->element << endl;
		printTree(t->right);
	 }
}

/*
 *template <class Comparable>
 *AvlTree<Comparable>::AvlNode * AvlTree<Comparable>::clone(AvlNode *t) const
 *{
 *    if (t == NULL)
 *        return NULL;
 *    else 
 *        return new AvlNode(t->element, clone(t->left), clone(t->right), 
 *                           t->height);
 *}
 */

